class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        """
        只要能复原出树本身
        更具每个节点的树深就可以很快速的计算距离了
        """
        """
        大意了 比如1->2 都是同一深度 但是距离就是2
        那还是图论
        初始化 是 每个节点只知道 与自己直接接触的节点(距离为1)
        然后根据相邻的节点 不断地更新自己 和其他节点的距离 直到接触不到新的节点
        因为路径是唯一的 所以一直选取最短的路径即可
        """
        """
        其实更为简便的方式应该是:
        保存树的边的关系
        节点就一层层向外拓展BFS 因为是一颗树没有环 那么向外拓展就不会有重复出现
        第一次出现点就是距离, 没有新的节点遇见就是拓展完成了
        
        超时了
        64 / 69 个通过测试用例
        """
        
#         N = len(edges)
#         node_num = N+1

#         tree = collections.defaultdict(list)
#         for n1, n2 in edges:
#             tree[n1].append(n2)
#             tree[n2].append(n1)

        
#         res = []
#         for i in range(node_num):
            
#             vis = [False] * node_num # 因为是无向边 标志位防止反向流动

#             dis = [-1] * node_num # 该点到各个节点的位置

#             # 举个i节点的例子

#             vis[i] = True
#             dis[i] = 0
#             queue = collections.deque()
#             for node in tree[i]:
#                 queue.append( (node, 1) )

#             while queue:
#                 node, d = queue.popleft()
#                 dis[node] = d
#                 vis[node] = True
#                 for idx in tree[node]:
#                     if vis[idx] == False:
#                         queue.append( (idx, d+1) )
            
#             res.append( sum(dis) )
        
#         return res
        """
        还是不能每个节点都重新跑,节点已经计算的距离要利用
        
        本质上 都是在填写 距离表格n^2 
        DFS 和 BFS本质上都一样 都是从单次从每个节点出发 遍历所有节点 
        这样就获得到其他节点的距离了
        所以直接DFS BFS肯定会超时
        
        看了官方的题解
        果然直接的DFS BFS会超时
        要用到已经计算的结果
        官方的思路就是 树形DP 没看懂
        看了题解中两次DFS的思路比较清晰
        """
        """
        虽然说边都是无向边,但是转为树,可以把边变为有向边,从父节点指向子节点
        而且题目里好像就是这样给边的.
        算了 还是处理一下 保证树生成正确
        """
        N = len(edges)
        node_num = N+1
        
        tree = collections.defaultdict(list)
        
        graph = collections.defaultdict(list)
        for n1, n2 in edges:
            graph[n1].append(n2)
            graph[n2].append(n1)
        
        #直接设0节点为root
        def generateTree(cur, farther):
            for node in graph[cur]:
                if node != farther:
                    tree[cur].append(node)
                    generateTree(node, cur)
                    
        generateTree(0, -1)
        
        subTreeDisSum = [0] * node_num
        subTreeCnt = [1] * node_num
        # 计算0节点的所有距离
        def calDis(root): # 返回包括 该点到子节点的距离和 / 该子树的所有节点数(包括root)
            disSum = 0
            childNum = 0 
            if root in tree:
                for node in tree[root]:
                    dSum, cNum = calDis(node)
                    disSum += dSum
                    childNum += cNum
            disSum += childNum
            childNum += 1 # root节点
            subTreeDisSum[root], subTreeCnt[root] = disSum, childNum
            return disSum, childNum
        
        calDis(0)
        # print(subTreeDisSum)
        # print(subTreeCnt)
        
        ans = [0] * node_num
        ans[0] = subTreeDisSum[0]
        def DFS(root):
            if root in tree:
                for node in tree[root]:
                    ans[node] = ans[root] - subTreeCnt[node] + node_num - subTreeCnt[node]
                    # 这个公式只表明相邻节点的关系
                    DFS(node)
        
        DFS(0)
        return ans
        
"""
这是目前费时最长的一道题目了
leetcode的题目大致是这样的
简单题：纯粹模拟就可以
中等题：熟悉一些算法和数据结构即可
难题：需要非常结合题目所给的条件，很具体的找出条件下的一些trick，要不然很难在时间或者空间上满足要求
这道题也是这样，需要了解到相邻节点间的关系才能重复利用已经计算过的结果，才能不超时，暴力BFS/DFS都超时了
mark这道题是因为这道题目十分的直观，正常人看到题目也会产生很多想法，
我也尝试了许多想法，最后发现方法基本上都是暴力BFS/DFS，必须要借用已经计算的答案
这个相邻节点关系的trick也是十分巧妙地
  0
 / \
1   2
   /|\
  3 4 5
比如 将树拆成两个子树  0，2分别为根节点 两个子树的内部的距离和  子树节点数分别为 dis(0) cnt(0) dis(2) cnt(2)
那么会发现 如果是计算ans(0) 只要组合两棵子树 就是将2节点连到0上，那么多出来的距离是"去每个节点路上都多走一段0->2"
就是比dis(2)本身多个cnt(2)
ans(0) = dis(0) + dis(2) + cnt(2)
同理 ans(2) = dis(2) + dis(0) + cnt(0)
会发现所有相邻节点间都有这个关系
那么从一点的答案就可以扩散到所有点，有了这个trick这个题目才解开
所以难题基本都限制在题目内了，不像中等题目，会共同训练一个算法或者数据结构了
"""
        